from alg import rob, rob_with_path, TreeNode
from gen import generate_test_cases, print_tree, tree_to_array, generate_binary_tree

def test_rob():

    print("=" * 60)
    print("打家劫舍III - 二叉树动态规划测试")
    print("=" * 60)
    
    test_cases = generate_test_cases()
    
    for i, (description, tree, expected) in enumerate(test_cases, 1):
        print(f"\n测试用例 {i}: {description}")
        print("-" * 40)
        
        if tree is None:
            print("树结构: 空树")
            result = rob(tree)
            print(f"最大盗取金额: {result}")
            if expected is not None:
                print(f"期望结果: {expected}")
                print(f"测试结果: {'✓ 通过' if result == expected else '✗ 失败'}")
        else:
            print("树结构:")
            print_tree(tree)
            print(f"数组表示: {tree_to_array(tree)}")
            
            # 测试基本算法
            result = rob(tree)
            print(f"最大盗取金额: {result}")
            
            # 测试带路径的算法
            amount, path = rob_with_path(tree)
            print(f"选择的房屋金额: {path}")
            print(f"路径总金额: {amount}")
            
            if expected is not None:
                print(f"期望结果: {expected}")
                print(f"测试结果: {'✓ 通过' if result == expected else '✗ 失败'}")


def test_manual_cases():
    """
    手动测试一些特殊情况
    """
    print("\n" + "=" * 60)
    print("手动测试特殊情况")
    print("=" * 60)
    
    # 测试用例1: 链状树（左偏）
    print("\n测试用例: 左偏链状树")
    print("-" * 30)
    root = TreeNode(10)
    root.left = TreeNode(5)
    root.left.left = TreeNode(3)
    root.left.left.left = TreeNode(1)
    
    print("树结构:")
    print_tree(root)
    result = rob(root)
    amount, path = rob_with_path(root)
    print(f"最大盗取金额: {result}")
    print(f"选择的房屋: {path}")
     
    print("\n测试用例: 右偏链状树")
    print("-" * 30)
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.right = TreeNode(3)
    root.right.right.right = TreeNode(4)
    
    print("树结构:")
    print_tree(root)
    result = rob(root)
    amount, path = rob_with_path(root)
    print(f"最大盗取金额: {result}")
    print(f"选择的房屋: {path}")
     
    print("\n测试用例: 完全二叉树")
    print("-" * 30)
    root = TreeNode(4)
    root.left = TreeNode(1)
    root.right = TreeNode(1)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(2)
    root.right.left = TreeNode(2)
    root.right.right = TreeNode(2)
    
    print("树结构:")
    print_tree(root)
    result = rob(root)
    amount, path = rob_with_path(root)
    print(f"最大盗取金额: {result}")
    print(f"选择的房屋: {path}")


def performance_test():
    """
    性能测试
    """
    print("\n" + "=" * 60)
    print("性能测试")
    print("=" * 60)
    
    import time
 
    depths = [5, 6, 7, 8]
    
    for depth in depths:
        print(f"\n测试深度为 {depth} 的随机树:")
        tree = generate_binary_tree(depth, 1, 100)
        
        start_time = time.time()
        result = rob(tree)
        end_time = time.time()
        
        print(f"最大盗取金额: {result}")
        print(f"执行时间: {(end_time - start_time) * 1000:.2f} ms")
 
        def count_nodes(node):
            if not node:
                return 0
            return 1 + count_nodes(node.left) + count_nodes(node.right)
        
        node_count = count_nodes(tree)
        print(f"节点数量: {node_count}")


def algorithm_explanation():

    print("\n" + "=" * 60)
    print("算法解释")
    print("=" * 60)
    


if __name__ == "__main__":
    # 运行所有测试
    algorithm_explanation()
    test_rob()
    test_manual_cases()
    performance_test()
    
    print("\n" + "=" * 60)
    print("测试完成！")
    print("=" * 60)